In various communications networks user information is carried in packets that are routed from the source to the destination via switches. A switch buffers each packet received from upstream sources until a decision is made when and to which outgoing link the packet need to be forwarded. Since the buffer space is always finite, packets could be dropped within a switch when buffer overflow occurs or when packets with a lower priority class have to give way to those with a higher priority class. In applications where a particular quality of service is desired or promised, it is obviously important for a switch to monitor packet losses incurred within the switch. Moreover, routing protocols require this information to be advertised within a network or a group of nodes, to facilitate path selections and to avoid congestion.
A high speed switch can generally be represented by a multi-stage interconnection where an N plurality of ingress modules are connected to a central switch fabric, and the outputs of the switch fabric are connected to an N plurality of egress modules. Each ingress and each egress module couples K input links and output links, respectively. Links carry streams of packets, where the destination of each packet is specified in the packet's header.
High speed switches of such construction typically include buffering within each of the elements (ingress modules, switching fabric, and egress modules). A packet received from an incoming link is first buffered at the ingress module, where a table lookup typically takes place to find out the egress module which the packet is destined to. In such an implementation, a local routing header will normally be placed in the front of the received packet. The local routing header may contain a number of information fields that are necessary to route the packet through the switching fabric, including the identity of the output link to which the packet needs to be routed. The extended packet is then dispatched to the desired egress module through the high speed, where some local buffering may be necessary. At the egress module, the packet is buffered until the outgoing link becomes available to transmit the packet. The local routing header is removed in the egress module before the packet is transmitted.
In a hierarchical communication network, a set of interconnected switches, each having the construction described above, can be unified in a logical group of nodes. From the network point of view, this logical group of nodes itself represents a generalized switch with input modules, output modules and generalized switching fabric. The network itself is a generalized switch on the highest level of hierarchy. Each logical group of nodes can maintain an internal routing header.
In this configuration, the packet could be lost in any of multiple locations within the ingress module, the switching fabric, or the egress module. The loss can be caused by buffer congestion, priority control, usage parameter control or a random electrical glitch leading to mis-routing, delineation error, checksum error, etc.
It is of practical interest, as indicated above, to be able to know whether, and how many, packets are lost within a switch or a logical group of nodes. It is of even greater interest to associate a packet loss with a particular traffic flow within the generalized switch.